package demo1;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: DELL
 * Date: 2023-08-04
 * Time: 10:24
 */
public class ShellSort {

    /**
     * gap > 1 时都是提前进行一些排序, 让数组更加趋于有序, 利于最后的插入排序
     * <p>
     * 由于 gap 无法直接准确确定, 希尔复杂度暂时按照 O(N^1.25 ~ 1.6 * N^1.25)
     * 空间复杂度 : O(1), 未开辟新的额外空间
     * 不稳定的排序
     *
     * @param array 排序数组
     */
    public static void shellSort(int[] array) {
        int gap = array.length;
        while (gap >= 1) {
            gap /= 2;
            shell(array, gap);
        }
    }

    /**
     * 希尔排序 - 通过步长提前对排序进行划分, 提前进行一定排序, 最后使用插入排序, 是插入排序的优化
     *
     * @param array 排序数组
     * @param gap   步长
     */
    private static void shell(int[] array, int gap) {
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i - gap;

            for (; j >= 0; j -= gap) {
                if (array[j] > tmp) {
                    array[j + gap] = array[j];
                } else {
                    break;
                }
            }
            array[j + gap] = tmp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {9, 1, 2, 5, 7, 4, 8, 6, 3, 5};
        ShellSort.shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
